最大割

Time Limit: 15 Sec Memory Limit: 256 MB

Description

考虑一张n个点的边带权无向图，点从1~ n编号。

对于图中的任意一个点集(可以为空集或是全集)，称所有那些恰好有一个端点在这个点集中的边所组成的边集为割。

我们再定义一个割的权值为:这个割中所含的所有边边权的异或和。
现在初始时给定一张n个点的空图，接下来会有若干次加(无向)边操作，每次加边后请你求出当前图中权值最大的割的权值。

Input

img

Output

img

Sample Input

3 6
　　1 2 1
　　1 2 1
　　3 3 111
　　1 3 101101
　　1 2 1011
　　2 3 111011

Sample Output

1
　　0
　　0
　　101101
　　101101
　　110000

HINT

l = log2(w)

img

Solution

首先我们发现，由于XOR满足消去律，那么我们定义一个新点的点权为该点所有连边的XOR和，那么任意点XOR起来得到的值正是割的值，所以这样操作之后问题就转化为了：任取几个点，求XOR出的最大值，支持点权修改。

那么我们现在显然得到了做法：线性基，并且我们需要维护一个可修改的线性基。

线性基的加入方法：1.从大到小加入，如果这一位没有匹配元则加入当前值当作匹配元，退出；2.如果这一位有匹配元了就XOR完向后继续执行操作，若值=0则退出。

线性基的最值方法：用一个初值为0的Ans串，从大到小贪心，如果这一位有匹配元并且Ans串该位为0则XOR，继续向后。

线性基的维护方法：我们另外记录一个record表示这个基是由哪些值XOR出来的，比如我们要消去b，然后我们就用一个 有bXOR出来且主元最小 的基来消去其它含b的基中的b，其中主元定义为最高位的1，我们让最高位的1最小，这样往上消去的时候依然可以满足XOR出来可以满足线性基的条件性质。然后我们扫一遍，如果含有这个b则XOR一下，并且record要XOR那个基的record，这样才可以保证record的记录不漏。

这道题就是先删除，然后再加入，每次询问求最值即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
using namespace std;

const int ONE = 2001;
const int L = 1005;

int T,n,x,y;
int PD;
char s[ONE];
int Link[ONE];

bitset <L> record[ONE],A[ONE];
bitset <L> Ans,P;

int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void Deal_first()
{
    scanf("%s",s+1);
    int len = strlen(s+1);
    P.reset();
    for(int i=1;i<=len;i++)
        P[L-len+i] = s[i]-'0';
}

void Add(int k)
{
    for(int pos=1;pos<=L;pos++)
        if(A[k][pos])
        {
            if(!Link[pos])
            {
                Link[pos] = k;
                break;
            }
            else
            {
                A[k] ^= A[Link[pos]];
                record[k] ^= record[Link[pos]];
                if(!A[k].any()) break;
            }
        }
}

void Update(int x)
{
    int k=0;
    for(int i=1;i<=n;i++)
        if(record[i][x] && !A[i].any())
        {
            k=i;
            break;
        }

    if(!k)
    {
        for(int i=L;i>=1;i--)
        {
            if(Link[i] && record[Link[i]][x])
            {
                k = Link[i];
                Link[i] = 0;
                break;
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(i!=k && record[i][x])
        {
            A[i] ^= A[k];
            record[i] ^= record[k];
        }
    }

    A[k] ^= P; Add(k);
}

int main()
{
    n=get();    T=get();
    for(int i=1;i<=n;i++) record[i][i] = 1;
    while(T--)
    {
        x=get();    y=get();
        Deal_first();
        Update(x);    Update(y);

        Ans.reset(); PD=0;
        for(int i=1;i<=L;i++)
        {
            if(Link[i] && !Ans[i]) Ans ^= A[Link[i]];
            if(Ans[i]) PD=1;
            if(PD) printf("%d",Ans[i]?1:0);
        }
        if(!PD) printf("0");
        printf("\n");
    }
}